package com.tgy.leetcode;

import java.util.HashMap;

/**
 * @Author: tgy
 * @Date: 12/25/20 9:11 AM
 *
 *  https://leetcode-cn.com/problems/lru-cache-lcci/
 */
public class _面试题_16_25_LRU_缓存 {


    private int capacity;

    private int size;

    private HashMap<Integer,Node> contaner;

    private Node font;

    private Node tail;

    private static class Node{

        Integer key;
        Integer value;

        private Node next;
        private Node pre;

        public Node(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }



    public _面试题_16_25_LRU_缓存(int capacity) {

        this.capacity = capacity;
        font = new Node();
        tail = new Node();

        font.next = tail;
        tail.pre = font;

        contaner = new HashMap<>();

    }

    public int get(int key) {

        Node node = contaner.get(key);

        if (node == null) {

            return -1;
        }

        addHead(node);
        return node.value;
    }

    public void put(int key, int value) {

        Node node = contaner.get(key);

        // 如果存在node，直接替换value
        if (node != null) {

            node.value = value;
            addHead(node);
            return;
        }

        // 判断size与capacity的关系
        if (size == capacity) {

            contaner.remove(removeTail());
        }

        Node newNode = new Node(key, value);

        // 添加到链表中
        newNode.next = font.next;
        font.next = newNode;
        newNode.next.pre = newNode;
        newNode.pre = font;

        // 添加到容器中
        contaner.put(key,newNode);
        size++;

    }

    private void addHead(Node node) {

        // 删除原来位置的node
        node.pre.next = node.next;
        node.next.pre = node.pre;

        // 添加到头部
        node.next = font.next;
        font.next = node;
        node.next.pre = node;
        node.pre = font;

    }

    private int removeTail() {

        Node node = tail.pre;
        node.pre.next = tail;
        tail.pre = node.pre;
        size--;
        return node.key;
    }
}
